#include <vector>

using namespace std;

// 情侣牵手
// n对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手
// 人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的ID
// 情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)
// 返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起
// 每次交换可选择任意两人，让他们站起来交换座位
// 测试链接 : https://leetcode.cn/problems/couples-holding-hands/

class Solution 
{
private:
    int sets;
    int father[31];

    void Build(int m)
    {
        for(int i = 0; i < m; ++i) father[i] = i;
        sets = m;
    }

    int Find(int i)
    {
        return i == father[i] ? i : father[i] = Find(father[i]);
    }

    void Union(int x, int y)
    {
        int fx = Find(x);
        int fy = Find(y);
        if(fx != fy)
        {
            father[fx] = fy;
            --sets; // 合并后，集合的数量就少了一个
        }
    }

public:
    int minSwapsCouples(vector<int>& row) 
    {
        int n = row.size();
        Build(n / 2);
        for(int i = 0; i < n; i += 2)
        {
            Union(row[i] / 2, row[i + 1] / 2);
        }
        return n / 2 - sets;
    }
};


// 并查集的另一种写法
class Solution 
{
public:
    int minSwapsCouples(vector<int>& row) 
    {
        int len = row.size();
        int n = len / 2;
        // ufs[i] < 0 时表示的是以 i 为父节点的集合大小
        // ufs[i] > 0 时表示的是 i 的父节点的编号 
        vector<int> ufs(n, -1);

        // 查找父节点的同时进行路径压缩
        function<int(int)> Find = [&](int x)
        {
            return ufs[x] < 0 ? x : ufs[x] = Find(ufs[x]);
        };

        for(int i = 0; i < len; i += 2)
        {
            int root1 = Find(row[i] / 2);
            int root2 = Find(row[i + 1] / 2);
            // 这里是合并两个集合
            if(root1 != root2)
            {
                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
            }
        }

        int ret = n;
        // ufs 中负数的个数就是集合的数量
        for(int i = 0; i < n; ++i)
        {
            if(ufs[i] < 0) --ret;
        }
        return ret;
    }
};